package nowcoder;

import java.util.*;

/**
 * 总体思想：
 * 1、先确定第一位的组合，然后确定第二位的组合
 * 2、如果到第n位，那第n位不动是一种组合，第n位和后面其他位调换又是一种组合，调换的前提是两个数不相同
 * @author tuyou_cd
 * @date 2021/4/25 16:07
 */
public class 数组元素排列组合 {

    public static List<List<Integer>> compute(List<Integer> num) {
        List<List<Integer>> result = new ArrayList<>();
        compute(num, 0, Collections.emptyList(), result);
        return result;
    }

    public static void compute(List<Integer> num, int index, List<Integer> cur, List<List<Integer>> result) {
        if (index == num.size()) {
            result.add(cur);
            return;
        }

        ArrayList<Integer> incrList = new ArrayList<>(cur);
        incrList.add(num.get(index));
        compute(num, index + 1, incrList, result);

        for (int i = index + 1; i < num.size(); i++) {
            if (num.get(index) != num.get(i)) {
                swap(num, index, i);
                incrList = new ArrayList<>(cur);
                incrList.add(num.get(index));
                compute(num, index + 1, incrList, result);
                swap(num, index, i);
            }
        }
    }

    public static void swap(List<Integer> list, int i1, int i2) {
        int temp = list.get(i1);
        list.set(i1, list.get(i2));
        list.set(i2, temp);
    }

    public static void main(String[] args) {
        System.out.println(compute(Arrays.asList(1, 5, 1)));
    }
}
